package leetcode_1301_1400;

import java.util.*;

public class LeeCode_1301 {
    public static void main(String[] args) {
        List<String> board = new ArrayList<>();
        board.add("E23");
        board.add("2X2");
        board.add("12S");
//        board.add("E11");
//        board.add("XXX");
//        board.add("11S");
        System.out.println(Arrays.toString(pathsWithMaxScore(board)));
    }
    private static class Node{
        public Node(long sum, long count) {
            this.sum = sum;
            this.count = count;
        }

        long sum;
        long count;
    }
    private static int[] pathsWithMaxScore(List<String> board) {
        long mod = (long) (1e9 + 7);
        int m = board.size(), n = board.get(0).length();
        boolean[][] vis = new boolean[m][n];
        vis[m - 1][n  - 1] = true;
        Node[][] dp = new Node[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = new Node(0, 0);
            }
        }
        dp[m - 1][n - 1].count = 1;
        int[][] dirs = new int[][]{{1, 0}, {1, 1}, {0, 1}};
        for (int i = m - 1; i >= 0; i--){
            for (int j = n - 1; j >= 0; j--){
                if (board.get(i).charAt(j) == 'X')
                    continue;
                int val = board.get(i).charAt(j) - '0';
                if (i == 0 && j == 0)
                    val = 0;
                boolean flag = false;
                for (int[] dir : dirs) {
                    int pi = i + dir[0];
                    int pj = j + dir[1];
                    if (pi < 0 || pi >= m || pj < 0 || pj >= n || board.get(pi).charAt(pj) == 'X' || !vis[pi][pj]){
                        continue;
                    }
                    flag = true;
                    Node now = dp[i][j];
                    Node pre = dp[pi][pj];
                    if (pre.sum + val > now.sum){
                        now.sum = pre.sum + val;
                        now.count = pre.count;
                    }else if (pre.sum + val == now.sum){
                        now.count += pre.count;
                        now.count %= mod;
                    }
                }
                if (flag)
                    vis[i][j] = true;
            }
        }
        return new int[]{(int) dp[0][0].sum, (int) dp[0][0].count};
    }
}